#ifndef ALGO_VEBTREE_H
#define ALGO_VEBTREE_H

#include "Map.h"
#include "PriorityQueue.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <sstream>
#include <iostream>

namespace algo {

  template <typename K>
  class VEBTreeNode : public PriorityQueueNode<K> {
  public:
    VEBTreeNode(K key) : key(key) {}

    K getKey() const { return key; }

  private:
    K key;
  };

  /**
   * K is the key-type
   * V is the valu-type
   * m is the upper bound integer size
   */
  template<typename K, typename V>
  class VEBTree : public Map<K, V>, public PriorityQueue<K> {
  private:
    typedef Pair<K, V> VEBNode;

  public:
    VEBTree(int m = 24) : PriorityQueue<K>("VEBTree"), children(0), aux(0),
      count(0), min(1 << m, V()), max(-1, V()), m(m), M(ceil(sqrt((double)(1 << m)))) { 

      if (m <= 0)
        return;
      
      children = new VEBTree*[M]; 

//      memset(children, 0, M*sizeof(VEBTree*));

      for (int i = 0; i < M; i++) {
        children[i] = new VEBTree(m/2);
      }

      aux = new VEBTree(m / 2);
    }

  public:
    virtual void insert(K key, V value) {
      VEBNode n(key, value);
      insert(n);
    }

    void insert(VEBNode &n) {
      if (!count++) {
        min = max = n;
        return;
      }

      if (n.l < min.l)
        std::swap(n, min);

      if (n.l > max.l)
        std::swap(n, max);

      if (count == 2)
        return;

      int i = n.l / M;

      if (children[i]->count == 0) {
        VEBNode v(i, n.r);
        aux->insert(v);
      }

      n.l %= M;
      children[i]->insert(n);
    }

    virtual V deleteKey(K key) { 
      count--;

      if (min.l == key && max.l == key) {
        V v = min.r;
        min = VEBNode(1 << (m/2), 0);
        max = VEBNode(-1, 0);
        return v;
      }
      if (key == min.l) {
        V v = min.r;
        if (aux->count == 0) {
          min = max;
          return v;
        } else {
          min = children[aux->min.l]->min;
          min.l += aux->min.l * M;
          children[aux->min.l]->deleteKey(min.l % M);
          if (children[aux->min.l]->count == 0)
            aux->deleteKey(aux->min.l);
          return v;
        }
      }
      if (key == max.l) {
        V v = max.r;
        if (aux->count == 0) {
          max = min;
          return v;
        } else {
          max = children[aux->max.l]->max;
          max.l += aux->max.l * M;
          children[aux->max.l]->deleteKey(max.l % M);
          if (children[aux->max.l]->count == 0)
            aux->deleteKey(aux->max.l);
          return v;
        }
      }

      int i = key / M;
      V v = children[i]->deleteKey(key % M);
      if (children[i]->count == 0) 
        aux->deleteKey(i);
      return v;
    }

    virtual V deleteMinimum() {
      return deleteKey(findMin().l);
    }

    virtual V lookup(K key) const {
      if (key == min.l)
        return min.r;

      if (key == max.l)
        return max.r;

      int i = key / M;
      return children[i]->lookup(key % M);
    }

    virtual Pair<K, V> findNext(K key) const {
      if (min.l == max.l)
        return min;
      if (key == max.l)
        return max;
      if (key <= min.l)
        return min;

      int i = key / M;
      int r = key % M;
      if (r <= children[i]->max.l)
        return children[i]->findNext(r);

      Pair<K, V> pair = aux->findNext(i+1);
      if (pair.l == i)
        return max;
      return children[pair.l]->min;
    }

    virtual Pair<K, V> findMin() const {
      return min;
    }

    size_t size() const { return count; }

    void dotString(std::ostringstream &out, int a = 0) {
      out << (size_t)this << " [label=\"Heap - m: " << m << "\"]\n";
      out << (size_t)&min << " [label=\"Node - k: " << (max.l == -1 ? min.l : min.l + a) << "\"]\n";
      out << (size_t)this << " -> " << (size_t)&min << " [label=\"min\"]\n";
      out << (size_t)&max << " [label=\"Node - k: " << (max.l == -1 ? -1 : max.l + a) << "\"]\n";
      out << (size_t)this << " -> " << (size_t)&max << " [label=\"max\"]\n";
      for (size_t i = 0; i < M; i++)
        if (children[i]->count) {
          out << (size_t)this << " -> " << (size_t)children[i] << "[label=\"" << i << "\"]\n";
          children[i]->dotString(out, a + i * M);
        }
      if (aux) {
        out << (size_t)this << " -> " << (size_t)aux << " [label=\"aux\"]\n";
        if (aux->max.l >= 0)
          aux->dotString(out);
      }
    }


    /** PriorityQueue implementation **/

    VEBTreeNode<K> *getMin() const {
      return new VEBTreeNode<K>(findMin().l);
    }

    VEBTreeNode<K> *insert(K key) {
      insert(key, V());
      return new VEBTreeNode<K>(key);
    }

    void decreaseKey(PriorityQueueNode<K> *node, K newKey) {
    }

    virtual K deleteMin() {
      K ret = findMin().l;
      deleteKey(findMin().l);
      return ret;
    }
    
    virtual void deleteNode(PriorityQueueNode<K> *node) {
      deleteKey(node->getKey());
      delete node;
    }

    ~VEBTree() {
      if (children) {
        for (int i = 0; i < M; i++)
          delete children[i];
        delete children;
        delete aux;
      }
    }


  private:
    size_t count;
    VEBNode min, max;
    VEBTree **children;
    VEBTree *aux;
    const int m, M;
  } 
#ifdef linux
  __attribute__((packed))
#endif
  ;
}

#endif //ALGO_VEBTREE_H
